package Link;

import java.util.HashMap;
import java.util.Map;

public class leet_160 {
    public static void main(String[] args) {
        ListNode tmp = new ListNode();
    }
}

class Solution_160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        return null;
    }

    /**
     * 解法思路：使用双指针来解决
     * 如果A与B具备相同结点时
     * A和B同时前进在走完一整轮后会在此相遇。
     * 假设 同一个链表是c
     * 那么 A = a + c
     * 那么 B = b + c
     * 那么我们让A走完后走B, B走完走A
     * 那么 A的路径就是 A = a+c+b
     * 那么 B的路径就是 B = b+c+a
     * 最后 他们注定会在一个地方遇见。
     * @param headA
     * @param headB
     * @return
     */
    public ListNode doubleSolve(ListNode headA, ListNode headB){
        if(headA==null || headB==null){return null;}
        ListNode me = headA;
        ListNode she = headB;
        while(me!=she){
            // me当A走完就把让它继续去B走
            // she当B走完就把让它继续去A走
            if(me==null){
                // 走完了我的路，我就去走你的路
                me = headB;
            }else {
                me = me.next;
            }

            if(she==null){
                // 走完了我的路，我就去走你的路
                she = headA;
            }else {
                she = she.next;
            }

        }
        return me;
    }

    /**
     * Hash解法程序员解法，符合实际但是没有浪漫的气息
     * @param headA
     * @param headB
     * @return
     */
    public ListNode hashSolve(ListNode headA, ListNode headB){
        // 建立关于其中一个的hash索引
        Map<ListNode, Integer> hashMap = new HashMap<>();
        ListNode currA = headA;
        ListNode currB = headB;
        while (currA!=null){
            hashMap.put(currA, 1);
            currA = currA.next;
        }

        // 存储同一个节点
        ListNode result =null;
        while(currB!=null){
            if(hashMap.containsKey(currB)){
                result = currB;
                break;
            }
            currB = currB.next;
        }
        return result;
    }

}
